問題

https://leetcode.com/problems/backspace-string-compare/description/

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation: Both s and t become "ac".

Example 2:
Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Example 3:
Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

Constraints:

• 1 <= s.length, t.length <= 200
• s and t only contain lowercase letters and '#' characters.

提示

Python 的 list 是comparable，可以直接用 list1 == list2 來判別兩個list是否相同．
但是 Go 的 Slices 不同，如果要判別兩個 Slices 是否相同，只能用 for 迴圈一一比對．
雖然也可以用 reflect.DeepEqual() 來達到相同目的，但是速度會慢很多．

偶的答案啦

使用兩個 stack 來解，
遇到 '#' 就 pop 最後一個元素，否則就 push 進stack
最後再比對兩個stack是否相同．

python

class Solution(object):
    def backspaceCompare(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        stack1, stack2 = "", ""
        for char in s:
            if char == '#':
                try:
                    stack1 = stack1[:-1]
                except IndexError:
                    continue
            else:
                stack1 += char

        for char in t:
            if char == '#':
                try:
                    stack2 = stack2[:-1]
                except IndexError:
                    continue
            else:
                stack2 += char

        return stack1 == stack2

go

func backspaceCompare(s string, t string) bool {
    stack1 := []byte{}
    stack2 := []byte{}
    for i := 0; i < len(s) ; i++ {
        if s[i] != '#' {
            stack1 = append(stack1, s[i])
        } else if len(stack1) > 0 {
            stack1 = stack1[:len(stack1)-1]
        }
    }

    for i := 0; i < len(t) ; i++ {
        if t[i] != '#' {
            stack2 = append(stack2, t[i])
        } else if len(stack2) > 0 {
            stack2 = stack2[:len(stack2)-1]
        }
    }

    if len(stack1) != len(stack2) {
        return false
    }

    for i := 0; i < len(stack1) ; i++ {
        if stack1[i] != stack2[i] {
            return false
        }
    }
    return true
}